#include "sort.h"

template <typename T>
void BubbleSort(vector<T> &vec){
    for (size_t i = 0; i < vec.size()-1; i++)
    {
        for (size_t j = 0; j < vec.size()-i-1; j++)
            if (vec[j]>vec[j+1])
                swap(vec[j],vec[j+1]);           
    }
    
}
template void BubbleSort(vector<int> &vec);

template <typename T>
void InsertSort(vector<T> &vec){
    for (size_t i = 1; i < vec.size(); i++)
    {
        T tmp=vec[i];
        size_t j=i-1;
        while (j>=0 && tmp<vec[j])
        {
            vec[j+1]=vec[j];
            j--;
        }
        vec[j+1]=tmp;      
    }    
}
template void InsertSort(vector<int> &vec);

template <typename T>
void SelectSort(vector<T> &vec){
    for (size_t i = 0; i < vec.size()-1; i++)
    {
        size_t minLoc=i;
        for (size_t j = i+1; j < vec.size(); j++)
        {
            if(vec[minLoc]>vec[j])minLoc=j;
        }
        swap(vec[i],vec[minLoc]);        
    }     
}
template void SelectSort(vector<int> &vec);


/**
 * @brief 快速排序
 * 
 * @tparam T 
 * @param vec 
 * @param low 
 * @param high 
 * @return int 
 */
template <typename T>
int partition(vector<T> &vec,int low,int high){
    int p=low,index=p+1;
    for (int i = p; i < high+1; i++)
    {
        if (vec[i]<vec[p])
        {
            if(i!=index)swap(vec[i],vec[index]);
            index++;
        }        
    }
    swap(vec[p],vec[index-1]);
    return index-1;    
}


template <typename T>
void QuickSort(vector<T> &vec,int left,int right){
    if(left<right){
        int mid=partition<T>(vec,left,right);
        QuickSort(vec,left,mid-1);
        QuickSort(vec,mid+1,right);
    }
}
template void QuickSort(vector<int> &vec,int left,int right);

/**
 * @brief 堆排序
 * 
 * @tparam T 
 * @param vec 
 * @param start 
 * @param end 
 */
template <typename T>
void sift(vector<T> &vec,int start,int end){
    int i=start,j=2*i+1;
    T tmp=vec[start];
    while (j<end)
    {
        if(j+1<end && vec[j]<vec[j+1])j++;

        if(tmp<=vec[j])swap(vec[i],vec[j]);
        
        i=j;
        j=2*i+1;
    }  
}

template <typename T>
void HeapSort(vector<T> &vec){

    for (int i = (vec.size()-1)/2; i > -1; i--){
        sift(vec,i,vec.size());
    }
    
    for (int i = vec.size()-1; i > 0; i--)
    {
        swap(vec[0],vec[i]);
        sift(vec,0,i);
    }   
}

template void HeapSort(vector<int> &vec);

template <typename T>
void IndexSift(vector<int> &index,vector<T> vec,int start,int end){
    int i=start;
    while (2*i+1<end)
    {
        int j=2*i+1;
        if(j+1<end && vec[index[j]]<vec[index[j+1]])j++;
        if(vec[index[i]]<vec[index[j]])swap(index[i],index[j]);
        i=j;
    }    
}

template <typename T>
vector<int> IndexHeapSort(vector<T> &vec){
    vector<int> index;
    for (int i = 0; i < vec.size(); i++)
    {
        index.push_back(i);
    }
    for (int i = (vec.size()-1)/2; i > -1; i--)
    {
        IndexSift(index,vec,i,vec.size());
    }
    for (int i = vec.size()-1; i >0; i--)
    {
        swap(index[0],index[i]);
        IndexSift(index,vec,0,i);
    }
    return index;  
}

template vector<int> IndexHeapSort(vector<int> &vec);

/**
 * @brief 归并排序
 * 
 * @tparam T 
 * @param vec 
 * @param left 
 * @param mid 
 * @param right 
 */
template <typename T>
void merge(vector<T> &vec,int left,int mid,int right){
    int i=left,j=mid+1,k=0;
    vector<T> tmpVec;
    while (i<mid && j<right)
    {
        if(vec[i]<vec[j]){
            tmpVec.push_back(vec[i]);
            i++;
        }else{
            tmpVec.push_back(vec[j]);
            j++;
        }
    }

    while (i<=mid)
    {
        tmpVec.push_back(vec[i]);
        i++;
    }

    while (j<right)
    {
        tmpVec.push_back(vec[j]);
        j++;
    }

    for (int i = left; i < right; i++)
    {
        vec[i]=tmpVec[i-left];
    }
}

template <typename T>
void MergeSort(vector<T> &vec,int left,int right){
    if(left<right){
        int mid=(left+right)/2;
        MergeSort(vec,left,mid);
        MergeSort(vec,mid+1,right);
        merge(vec,left,mid,right);
    }
}
template void MergeSort(vector<int> &vec,int left,int right);
